home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 10 - 1994 / 10.11 Nov 94 / Programmers' Challenge / scribble.c < prev   
Encoding:
C/C++ Source or Header  |  1994-09-12  |  14.7 KB  |  473 lines  |  [TEXT/KAHL]
  1. /* EraseScribble
  2.  *  Copyright (c) 1994  J Robert Boonstra
  3.  *
  4.  * Problem statement:
  5.  *
  6.  * Determine whether a square eraser of diameter eraserSize
  7.  * centered at the thePoint intersects any of the points
  8.  * in the data structure theScribble.  Note that while the
  9.  * problem statement refers to line segments, the definition
  10.  * of a "hit" means that only the endpoints matter.
  11.  *
  12.  * Solution strategy:
  13.  *
  14.  * The ideal approach would be to create a simple bitMap
  15.  * during Initialization indicating whether an eraser at a
  16.  * given location intersected theScribble.
  17.  * The bitMap would be created by stamping a cursor image
  18.  * at the location of each point in theScribble.
  19.  * However, a bitMap covering the required maximum bounding
  20.  * box of 1024 x 1024 would require 2^17 bytes, or four
  21.  * times as much storage as the 32K we are allowed to use.
  22.  *
  23.  * Therefore, this solution has three cases:
  24.  * 1) If the actual bounding box for theScribble passed to
  25.  *    the init function fits in the 32K available, we
  26.  *    create a bitMap as above and use it directly.
  27.  * 2) Otherwise, we attempt to create a half-scale bitMap,
  28.  *    where each bit represents 4 pixels in the image, 2 in
  29.  *    .h  and 2 in .v.  In the PtInScribble function, we can
  30.  *    then quickly determine in most cases when the eraser
  31.  *    does not intersect theScribble, and we have to walk
  32.  *    the points in theScribble if the bitMap indicates a
  33.  *    possible hit.
  34.  * 3) In the event there is not enough storage for a
  35.  *    half-scale bitmap, we create a quarter-scale bitmap,
  36.  *    where each bit represents 16 pixels in the image, 4
  37.  *    in .h and 4 in .v.  Then we proceed as in case 2.
  38.  *
  39.  * To optimize examination of the points in theScribble
  40.  * when the bitmap is not full scale, we sort the points
  41.  * in the initialization function and store them in the
  42.  * privateScribbleDataPtr.  Although this reduces the amount
  43.  * of storage available for the bitmap by ~2K, it improves
  44.  * worst case performance significantly.
  45.  *
  46.  * Although the init function is not timed for score, we
  47.  * have written it in assembler, in the spirit of the
  48.  * September Challenge.
  49.  */
  50.  
  51. #pragma options(assign_registers,honor_register,mc68020)
  52.  
  53. /*
  54.  * Typedefs, defines, and prototoypes
  55.  */
  56.  
  57. #define ushort unsigned short
  58. #define ulong  unsigned long
  59. #define kTotalStorage  0x8000
  60. /*
  61.  * Layout of privateScribbleData storage:
  62.  *  OFFSET                                   CONTENT
  63.  *  ------                                   -------
  64.  *    0:                                    bitMap
  65.  *    kTotalStorage-kGlobals-4*gNumPoints:  sorted points
  66.  *    kTotalStorage-kGlobals:               global data
  67.  *
  68.  * Globals stored in PrivateScribbleDataPtr
  69.  *   gNumPoints:number of points in the scribble
  70.  *   gHOrigin:  min scribble h - eraserSize/2
  71.  *   gVOrigin:  min scribble v - eraserSize/2
  72.  *   gBMHeight: max scribble h - min scribble h + eraserSize
  73.  *   gBMWidth:  max scribble v - min scribble v + eraserSize
  74.  *   gRowBytes: bitMap rowBytes
  75.  *   gMode:     flag indicating bitmap scale
  76.  */
  77. #define gNumPoints    kTotalStorage-2
  78. #define gHOrigin      kTotalStorage-4
  79. #define gVOrigin      kTotalStorage-6
  80. #define gBMHeight     kTotalStorage-8
  81. #define gBMWidth      kTotalStorage-10
  82. #define gRowBytes     kTotalStorage-12
  83. #define gMode         kTotalStorage-14
  84. #define kGlobals                    14
  85. #define kSortedPoints kTotalStorage-kGlobals
  86. #define   kBitMap           0
  87. #define   kHalfscaleBitMap  1
  88. #define   kQrtrscaleBitMap -1
  89.  
  90. typedef struct Scribble {
  91.   Point startingPoint;
  92.   Point deltaPoints[1];
  93. } Scribble, *ScribblePtr, **ScribbleHndl;
  94.  
  95. void *EraseScribbleInit(ScribbleHndl theScribble,
  96.       unsigned short eraserSize);
  97.  
  98. Boolean PtInScribble(Point thePoint,
  99.       ScribbleHndl theScribble,
  100.       unsigned short eraserSize,
  101.       void *privateScribbleDataPtr);
  102.  
  103.  
  104. /*
  105.  * ------------------------------------------- PtInScribble
  106.  */
  107. #define eraserH       D0
  108. #define eraserV       D1
  109. #define eraserSz      D2
  110. #define pointCt       D6
  111. #define scribblePt    D7
  112.  
  113. Boolean PtInScribble(Point thePoint,
  114.       ScribbleHndl theScribble,
  115.       unsigned short eraserSize,
  116.       void *privateScribbleDataPtr)
  117. {
  118.   asm 68020 {
  119.     MOVEM.L    D6-D7,-(A7)
  120.     MOVE.L    thePoint,D1
  121.     MOVEA.L   privateScribbleDataPtr,A0
  122.     MOVEQ     #0,D0           ; clear high bits for BFTST
  123.     MOVE.W    D1,D0
  124.     SWAP      D1
  125. ; Return noHit if eraser is outside bounding box defined
  126. ; by gVOrigin,gHOrigin,gVOrigin+gBMHeight,gHOrigin+gBMWIdth.
  127. ; Note that the bounding box has already been expanded by
  128. ; eraserSize/2 in each direction.
  129.     SUB.W     gVOrigin(A0),D1
  130.     BLT       @noHit          ; v < boundingBox.top
  131.     CMP.W     gBMHeight(A0),D1
  132.     BGT       @noHit          ; v > boundingBox.bottom
  133.     SUB.W     gHOrigin(A0),D0
  134.     BLT       @noHit          ; h < boundingBox.left
  135.     CMP.W     gBMWidth(A0),D0
  136.     BGT       @noHit          ; h > boundingBox.right
  137. ;
  138. ; Check eraser against bitMap; return noHit if not set
  139. ;
  140.     MOVE.W    gRowBytes(A0),D2
  141.     TST.W     gMode(A0)
  142.     BNE.S     @testQrtrScaleBitMap
  143. ;
  144. ; Full-scale bitMap case; can return Hit if bit is set
  145. ;
  146.     MULU.W    D1,D2      ; multiple row by rowBytes
  147.     ADDA      D2,A0      ; A0 points to correct bitMap row
  148.     BFTST     (A0){D0:1} ; D0 contains bit offset
  149.     BNE       @hit
  150. noHit:
  151.     MOVEQ     #0,D0
  152.     MOVEM.L   (A7)+,D6-D7
  153.     UNLK      A6     ; save one branch by returning directly
  154.     RTS
  155. testQrtrScaleBitMap:
  156.     BGT       @testHalfScaleBitMap
  157. ;
  158. ; Qrtr-scale bitMap case; cannot always return Hit if set
  159. ;
  160.     LSR.W     #2,D1      ; * adjust for qrtr-scale bitmap *
  161.     LSR.W     #2,D0      ; * adjust for qrtr-scale bitmap *
  162.     MULU.W    D1,D2      ; multiple row by rowBytes
  163.     ADDA      D2,A0      ; A0 points to correct bitMap row
  164.     BFTST     (A0){D0:1}
  165.     BEQ       @noHit
  166.     BRA.S     @TestPoints
  167. testHalfScaleBitMap:
  168. ;
  169. ; Half-scale bitMap case; cannot always return Hit if set
  170. ;
  171.     LSR.W     #1,D1      ; * adjust for half-scale bitmap *
  172.     LSR.W     #1,D0      ; * adjust for half-scale bitmap *
  173.     MULU.W    D1,D2      ; multiple row by rowBytes
  174.     ADDA.L    D2,A0      ; A0 points to correct bitMap row
  175.     BFTST     (A0){D0:1}
  176.     BEQ       @noHit
  177. TestPoints:
  178. ;
  179. ; bitMap indicates there might be a hit, need to check
  180. ;
  181.     MOVEA.L   privateScribbleDataPtr,A0
  182.     MOVE.W    eraserSize,eraserSz
  183.     MOVE.L    thePoint,eraserH
  184.     MOVE.L    eraserH,eraserV
  185.     SWAP      eraserV
  186.     LEA       kSortedPoints(A0),A1
  187. ; Scan sets of 64 points to find a close match
  188.     MOVE.W    gNumPoints(A0),D7
  189.     LSR.W     #6,D7       ; numPoints/64
  190.     MOVE.W    D7,pointCt
  191.     LSL.W     #8,D7       ; times 4 bytes/pt * 64 pts
  192.     SUBA.L    d7,A1
  193.     SUBQ      #1,pointCt
  194. eightLoop:
  195.     MOVE.L    -(A1),scribblePt
  196.     CMP.W     eraserH,scribblePt
  197.     BLT.S     @hLoop
  198.     ADDI      #65*4,A1
  199.     DBRA      pointCt,@eightLoop;
  200. ; Note that the sorted scribblePts have been stored with
  201. ; eraserSize/2 already added in h and v
  202. hLoop:
  203.     MOVE.L    -(A1),scribblePt
  204.     CMP.W     eraserH,scribblePt
  205.     BLT.S     @hLoop
  206. ; All points from here on have a true .h component >=
  207. ; eraserH-eraserSize/2.  Now need to look at those where
  208. ; .h <= eraserH+eraserSize/2.  Because we already added
  209. ; eraserSize/2 to the sorted point values, we compare
  210. ; against eraserH+eraserSz
  211.     ADD.W     eraserSz,eraserH
  212.     ADD.W     eraserV,eraserSz
  213. vLoop:
  214.     CMP.W     eraserH,scribblePt
  215.     BGT.S     @noHit
  216. ; scribblePt.h is in range, now check .v
  217.     SWAP      scribblePt
  218.     CMP.W     eraserV,scribblePt
  219.     BLT.S     @vLoopCheck
  220.     SUB.W     eraserSz,scribblePt
  221.     BLE.S     @hit
  222. vLoopCheck:
  223.     MOVE.L    -(A1),scribblePt
  224.     BRA       @vLoop;
  225.  
  226. hit:
  227.     MOVEQ     #1,D0
  228.     MOVEM.L   (A7)+,D6-D7
  229.   }
  230. }
  231.  
  232. /*
  233.  * -------------------------------------- EraseScribbleInit
  234.  */
  235. void *EraseScribbleInit(ScribbleHndl theScribble,
  236.       unsigned short eraserSize)
  237. {
  238. ulong bitMapStorageAvail;
  239.   asm 68020 {
  240.     MOVEM.L   D3-D7/A2,-(A7)
  241. ; Allocate storage - use full 32K.
  242. ; Note that it is the responsibility of the caller to
  243. ; release this storage.
  244.     MOVE.L    #kTotalStorage,D0
  245.     NewPtr    CLEAR
  246.     MOVE.L    A0,A2    ; A0 is privateDataPtr
  247. ; Scan thru the scribble to find min and max in h and v
  248.     MOVEA.L   theScribble,A1
  249.     MOVEA.L   (A1),A2  ; A2 = *theScribble
  250. ; Initialize mins and maxes to be the starting point
  251.     MOVE.L    (A2)+,D7 ; current scribble point
  252.     MOVEQ     #0,D5    ; clear high bits for ADDA.L later
  253.     MOVE.W    D7,D5    ; D5 = max h
  254.     MOVE.W    D7,D4    ; D4 = min h
  255.     MOVE.W    D7,D1    ; D1 = current h
  256.     SWAP      D7       ; D7 = max v
  257.     MOVE.W    D7,D6    ; D6 = min
  258.     MOVE.W    D7,D2    ; D2 = current v
  259.     LEA       kSortedPoints(A0),A1; sorted point storage
  260. ; Set up eraserSize/2
  261.     MOVE.W    eraserSize,D3
  262.     LSR.W     #1,D3    ; D3 = eraserSize/2
  263. minMaxLoop:
  264. ; Store point for subsequent sorting
  265.     MOVE.W    D1,D0
  266.     ADD.W     D3,D0
  267.     MOVE.W    D0,-(A1) ; store current h + eraserSize/2
  268.     MOVE.W    D2,D0
  269.     ADD.W     D3,D0
  270.     MOVE.W    D0,-(A1) ; store current v + eraserSize/2
  271. ; Fetch next point
  272.     MOVE.L    (A2)+,D0 ; fetch deltaPoint
  273.     BEQ       @minMaxDone
  274.     ADD.W     D0,D1    ; update current h
  275.     CMP.W     D1,D5
  276.     BGE       @noNewHMax
  277.     MOVE.W    D1,D5    ; store new max h
  278.     BRA.S     @noNewHMin
  279. noNewHMax:
  280.     CMP.W     D1,D4
  281.     BLE       @noNewHMin
  282.     MOVE.W    D1,D4    ; store new min h
  283. noNewHMin:
  284.     SWAP      D0
  285.     ADD.W     D0,D2    ; update current v
  286.     CMP.W     D2,D7
  287.     BGE       @noNewVMax
  288.     MOVE.W    D2,D7    ; store new max v
  289.     BRA.S     @noNewVMin
  290. noNewVMax:
  291.     CMP.W     D2,D6
  292.     BLE       @noNewVMin
  293.     MOVE.W    D2,D6    ; store new min v
  294. noNewVMin:
  295.     BRA.S     @minMaxLoop
  296. minMaxDone:
  297.  
  298. ; Calculate number of points
  299.     LEA       kSortedPoints(A0),A2
  300.     MOVE.L    A2,D0
  301.     SUB.L     A1,D0
  302.     LSR.W     #2,D0
  303.     MOVE.W    D0,gNumPoints(A0)
  304. ; Calculate bitmap storage available
  305.     SUBQ.L    #8,A1    ; Reserve room for sentinals
  306.     MOVE.L    A1,D0
  307.     SUB.L     A0,D0
  308.     MOVE.L    D0,bitMapStorageAvail
  309. ; Calculate origin = min h/v minus eraserSize/2
  310.     MOVE.W    eraserSize,D0
  311. ; Calculate number of columns
  312.     SUB.W     D3,D4    ; adjust h origin for eraserSize/2
  313.     MOVE.W    D4,gHOrigin(A0) ; D4 = H Origin
  314.     ADD.W     D0,D5    ; add eraserSize to width
  315.     SUB.W     D4,D5
  316.     MOVE.W    D5,gBMWidth(A0)
  317.     ADDQ      #7,D5    ; round up to byte level
  318.     LSR.W     #3,D5
  319.     MOVE.W    D5,gRowBytes(A0) ; D5 = rowBytes
  320. ; Calculate number of rows
  321.     SUB.W     D3,D6    ; adjust v origin for eraserSize/2
  322.     MOVE.W    D6,gVOrigin(A0) ; D6 = V Origin
  323.     ADD.W     D0,D7    ; add eraserSize to height
  324.  
  325.     SUB.W     D6,D7
  326.     MOVE.W    D7,gBMHeight(A0) ; D7 = number of rows
  327.     ADDQ      #1,D7
  328. ; Calculate number of bytes needed to store bitmap.
  329.     MULU.W    D5,D7
  330.     CMP.L     bitMapStorageAvail,D7
  331.     BLE.S     @haveEnoughStorage
  332. ;
  333. ; Not enough storage, so we try a half-scale bitMap
  334. ;
  335.     MOVEQ     #kHalfscaleBitMap,D1
  336.     MOVE.W    D1,gMode(A0)
  337. ; Adjust gRowBytes for half-scale bitMap
  338.     MOVE.W    gBMWidth(A0),D5
  339.     ADDI      #15,D5   ; round up to byte level
  340.     LSR.W     #4,D5
  341.     MOVE.W    D5,gRowBytes(A0) ; D5 = rowBytes
  342.     LSR.W     #1,D0    ; adjust eraser size
  343.                        ;   for half-scale bitmap
  344.     MOVE.W    gBMHeight(A0),D7
  345.     ADDQ      #1,D7
  346.     LSR.W     #1,D7
  347.     ADDQ      #1,D7
  348.     MULU.W    D5,D7
  349.     CMP.L     bitMapStorageAvail,D7
  350.     BLE.S     @haveEnoughStorage
  351. ;
  352. ; Still not enough storage, so we set up a qrtr-scale bitMap
  353. ;
  354.     MOVEQ     #kQrtrscaleBitMap,D1
  355.     MOVE.W    D1,gMode(A0)
  356. ; Adjust gRowBytes for qrtr-scale bitMap
  357.     MOVE.W    gBMWidth(A0),D5
  358.     ADDI      #31,D5    ; round up to byte level
  359.     LSR.W     #5,D5
  360.     MOVE.W    D5,gRowBytes(A0) ; D5 = rowBytes
  361.     LSR.W     #1,D0    ;  adjust eraser size
  362.                        ;   for qrtr-scale bitmap
  363.  
  364. haveEnoughStorage:
  365. ;
  366. ; Create bitMap
  367. ;
  368.     MOVEA.L   theScribble,A1
  369.     MOVEA.L   (A1),A2
  370. ;
  371. ; Initial location to stamp eraser image in bitmap is the
  372. ; startingPoint, minus the bitmap origin, minus eraserSize/2
  373. ;
  374.     MOVE.L    (A2)+,D2 ; Fetch startingPoint
  375.     MOVE.W    D2,D1    ; D1 = current scribble point h
  376.     SWAP      D2       ; D2 = current scribble point v
  377.     SUB.W     D4,D1    ; D1 = scribble point h - H origin
  378.     SUB.W     D3,D1    ; offset h by -eraserSize/2
  379.     SUB.W     D6,D2    ; D2 = scribble point v - V origin
  380.     SUB.W     D3,D2    ; offset v by -eraserSize/2
  381.     MOVEQ     #0,D4    ; clear high bits for BFINS later
  382.  
  383.     MOVE.W    D0,D7    ; save eraser width
  384.  
  385.     MOVEQ     #-1,D3   ; set bits for insertion using BFINS;
  386. ; Loop through all points in the scribble
  387. ;
  388. stampPointLoop:
  389.     MOVEA.L   A0,A1
  390.     MOVE      D7,D6    ; D6 = row counter for DBRA smear
  391.  
  392.     MOVE.W    D2,D0    ; D0 = v - origin
  393.  
  394.     TST.W     gMode(A0)
  395.     BEQ       @L1
  396.     BGT       @L0
  397.     LSR.W     #1,D0    ; adjust for qrtr-scale bitmap
  398. L0: LSR.W     #1,D0    ; adjust for half-scale bitmap
  399. L1:
  400.     MULU.W    D5,D0    ; D0 = (v - origin) * rowBytes
  401.     ADDA.L    D0,A1    ; A1 = privateStorage - rowOffset
  402.     MOVE.W    D7,D0
  403.     ADDQ      #1,D0    ; D0 = eraserSize/2+1, the number of
  404.                        ;   bits to set in bitMap;
  405. ;
  406. ;   Loop through eraserSize+1 rows in bitMap for this point
  407. ;
  408. stampRowLoop:
  409.     MOVE.W    D1,D4    ; D4 = scribble h - origin
  410.  
  411.     TST.W     gMode(A0)
  412.     BEQ       @L3
  413.     BGT       @L2
  414.     LSR.W     #1,D4    ; adjust for qrtr-scale bitmap
  415. L2: LSR.W     #1,D4    ; adjust for half-scale bitmap
  416. L3:
  417.     BFINS     D3,(A1){D4:D0} ; insert mask D3 of width D0
  418.                              ;   into bitmap A1 at offset D4
  419.     ADDA.L    D5,A1          ; increment by rowBytes
  420.     DBRA      D6,@stampRowLoop
  421. ;
  422. ;   Fetch next deltaPoint, quit if done
  423. ;
  424.     MOVE.L    (A2)+,D0
  425.     BEQ       @bitMapDone
  426.     ADD.W     D0,D1    ; update current scribble h
  427.     SWAP      D0
  428.     ADD.W     D0,D2    ; update current scribble v
  429.     BRA.S     @stampPointLoop
  430.  
  431. bitMapDone:
  432. ;
  433. ; Sort scribble points for fast lookup.  Simple exchange
  434. ; sort will do.
  435. ;
  436. outerSortLoop:
  437.     MOVEQ     #0,D6    ; exchange flag = no exchanges
  438.     LEA       kSortedPoints(A0),A2; sorted point storage
  439.     MOVE.W    gNumPoints(A0),D7 ;outer loop counter
  440.     SUBQ     #2,D7    ; DBRA adjustment
  441.     MOVE.L    -(A2),D0 ; D0 = compare value - h
  442.     MOVE.L    D0,D1
  443.     SWAP      D1       ; D1 = compare value - v
  444. innerSortLoop:
  445.     MOVE.L    -(A2),D2
  446.     MOVE.L    D2,D3
  447.     SWAP      D3
  448.     CMP.W     D0,D2    ; primary sort by h
  449.     BLT.S     @doSwap
  450.     BGT.S     @noSwap
  451.     CMP.W     D1,D3    ; secondary sort by v
  452.     BGE.S     @noSwap
  453. doSwap:
  454.     MOVE.L    D2,4(A2)
  455.     MOVE.L    D0,(A2)
  456.     MOVEQ     #1,D6
  457.     BRA.S     @testInnerLoop
  458. noSwap:
  459.     MOVE.L    D2,D0
  460.     MOVE.W    D3,D1
  461. testInnerLoop:
  462.     DBRA      D7,@innerSortLoop
  463.     TST.W     D6
  464.     BNE.S     @outerSortLoop;
  465.     MOVE.L    #0x80008000,-(a2) ; Sentinal to end point loop
  466.     MOVE.L    #0x7FFF7FFF,-(a2) ; Sentinal to end point loop
  467.  
  468.     MOVE.L    A0,D0    ; return pointer to private data
  469.     MOVEM.L   (A7)+,D3-D7/A2
  470.   }
  471. }
  472.  
  473.